package org.chen.interview.huawei;

import java.util.*;

/**
 * @Author chen
 * @Date 2023/7/4 20:09
 *
 * 题目名称：
 * 题目描述：
 * 给你一个长度为 2 * n 的整数数组。你需要将 nums 分成 两个 长度为 n 的数组，分别求出两个数组的和，并 最小化 两个数组和之 差的绝对值 。nums 中每个元素都需要放入两个数组之一。
 * 请你返回 最小 的数组和之差。
 *
 * 示例 1：
 * 输入：nums = [3,9,7,3]
 * 输出：2
 * 解释：最优分组方案是分成 [3,9] 和 [7,3] 。
 * 数组和之差的绝对值为 abs((3 + 9) - (7 + 3)) = 2 。
 *
 * 示例 2：
 * 输入：nums = [-36,36]
 * 输出：72
 * 解释：最优分组方案是分成 [-36] 和 [36] 。
 * 数组和之差的绝对值为 abs((-36) - (36)) = 72 。
 *
 * 示例 3：
 * 输入：nums = [2,-1,0,4,-2,-9]
 * 输出：0
 * 解释：最优分组方案是分成 [2,4,-9] 和 [-1,0,-2] 。
 * 数组和之差的绝对值为 abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0 。
 *
 * 提示：
 *     1 <= n <= 15
 *     nums.length == 2 * n
 *     -107 <= nums[i] <= 107
 */
public class GroupDivideMinValue {
    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        List<Integer> personList = new ArrayList<>();
//        while (in.hasNextInt()) { // 注意 while 处理多个 case
//            int a = in.nextInt();
//            personList.add(a);
//        }
        List<Integer> personList = new ArrayList();
        personList.add(10);
        personList.add(9);
        personList.add(8);
        personList.add(7);
        personList.add(6);
        personList.add(5);
        personList.add(4);
        personList.add(3);
        personList.add(2);
        personList.add(1);
        System.out.println(divideMini(personList));
    }

    /**
     * 10人分为两队每队5人，战力之差最小
     * 相对平衡
     */
    public static int divideMini(List<Integer> personList){

        int mini=0;
        List<Integer> fList = new ArrayList<>();
        List<Integer> sList = new ArrayList<>();
        int avg = (sum(personList)/personList.size());
        int size = personList.size()/2;
        // 分为两队
        for(int i=0 ;i<personList.size() && fList.size()<=size; i++){
            //分队依据，两个list之和趋于他们的平均数,所有数据到平均值的距离
            if(personList.get(i)>=avg && fList.size()<size-1){
                int temp = Math.abs(personList.get(i) -avg);
                fList.add(personList.get(i));
                personList.remove(i);
                int midex = 0;
                int mivalueToTemp =temp;
                for(int j=0 ;j<personList.size(); j++){
                    if(personList.get(j)<avg) {
                        int distance = Math.abs(personList.get(j) - avg);
                        if (distance >= mivalueToTemp) {
                            mivalueToTemp = distance;
                            midex = j;
                        }
                    }
                }
                fList.add(personList.get(midex));
                personList.remove(midex);
            }else if(personList.get(i)>=avg){
                fList.add(personList.get(i));
                personList.remove(i);
            }

        }
        sList =personList;
        mini = Math.abs(sum(fList)-sum(sList));
        // 计算两队的差值
        return mini;
    }

    public static int sum(List<Integer> personList){
        int sumValue =0;
        for(Integer item : personList){
            sumValue = sumValue+item;
        }
        return sumValue;
    }

    public static int min(List<Integer> personList){
        int index =0;
        int minValue = 0;
        for(int i=0 ;i<personList.size(); i++){
            if(minValue > personList.get(i)){
                minValue = personList.get(i);
                index = i;
            }
        }
        return index;
    }

    public static int minimumDifference(int[] nums) {
        int n = nums.length/2 ;
        int sum = Arrays.stream(nums).sum();
        int[] A = new int[n],B=new int[n];
        List<List<Integer>> X = new ArrayList<>(),Y = new ArrayList<>();

        //分割两个子集
        for(int i=0;i<=n;i++){
            if(i<n){
                A[i] = nums[i];
                B[i] = nums[i+n];
            }
            X.add(new ArrayList<>());
            Y.add(new ArrayList<>());
        }

        //进行组合枚举
        for(int mask = 0; mask<1<<n;mask++){
            int key = Integer.bitCount(mask);
            int cnt_a =0,cnt_b=0;
            for(int i=0;i<n;i++){
                if(((mask>>i)&1)==1){
                    cnt_a += A[i];
                    cnt_b += B[i];
                }
            }
            X.get(key).add(cnt_a);
            Y.get(key).add(cnt_b);
        }

        // 将Y进行排序，用于二分查找
        for(int i=0;i<=n;i++){
            Collections.sort(Y.get(i));
        }

        //进行二分查找答案
        int ans = Integer.MAX_VALUE;
        for(int k=0;k<=n;k++){
            List<Integer> x = X.get(k);
            List<Integer> y = Y.get(n-k);
            for(int i:x){
                int l =0,r=y.size()-1;
                while (l<r){
                    int mid = (r-1)/2+1;
                    int j = y.get(mid);
                    if(i+j<sum/2){
                        l=mid+1;
                    }
                    else{
                        r = mid;
                    }
                }
                ans = Math.min(ans,Math.abs(sum-i-y.get(l)-(i+y.get(l))));
            }
        }
        return ans;
    }

}